/*
 * @lc app=leetcode.cn id=260 lang=cpp
 *
 * [260] 只出现一次的数字 III
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // x ^ x = 0, x ^ 0 = x
        int tmp = 0;
        for(auto n : nums)
        {
            tmp ^= n;
        }

        // 假设 两个只出现一次的数字分别为 x 和 y 则此时有 tmp == x ^ y
        int lsb = 0;
        for(int i = 0; i < 32; i++)
        {
            if(tmp & (1 << i))
            {
                lsb = tmp & (1 << i);
            }
        }

        int x = 0, y = 0;
        for(auto n:nums)
        {
            if(n & lsb)
            {
                x ^= n;
            }
            else
            {
                y ^= n;
            }
        }

        return {x, y};
    }
};
// @lc code=end

